#pragma once
#include<iostream>
using namespace std;


template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K, V>* _left;
	BSTNode<K, V>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree
{
	using Node = BSTNode<K>;
public:
	bool insert(const K& key)
	{
		if (nullptr = _root)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = _root;
		while (cur != nullptr)
		{
			parent = cur;
			if (key > cur->_val)
				cur = cur->_right;
			else if (key < cur->_val)
				cur = cur->_left;
			else
				return false;
		}
		
		if (key > parent->_val)
			parent->_right = new Node(key);
		else
			parent->_left = new Node(key);

		return true;
	}

	Node* find(const K& key)
	{
		if (nullptr == _root)
			return nullptr;

		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_val == key)
				return cur;

			if (key > cur->_val)
				cur = cur->_right;
			else
				cur = cur->_left;
		}
		return nullptr;
	}

	bool erase(const K& key)
	{
		Node* parent = _root;
		Node* cur = _root;

		while (cur != nullptr)
		{
			parent = cur;
			if (key > cur->_val)
				cur = cur->_right;
			else if (key < cur->_val)
				cur = cur->_left;
			else
				break;
		}

		if (!cur)
			return false;

		if (!(cur->_left && cur->_right))
		{
			if (cur == _root)
			{
				if (cur->_left)
					_root = cur->_left;
				else
					_root = cur->_right;

			}
			else
			{
				if (parent->_left == cur)
				{
					if (cur->_left)
						parent->_left = cur->_left;
					else
						parent->_left = cur->_right;
				}
				else
				{
					if (cur->_left)
						parent->_right = cur->_left;
					else
						parent->_right = cur->_right;
				}
			}
			delete cur;
			cur = nullptr;
		}
		else
		{
			Node* fast = cur->_left;
			Node* slow = cur;
			while (fast->_right)
			{
				slow = fast;
				fast = fast->_right;
			}
			swap(fast->_val, cur->_val);
			
			if (slow->_right == fast)
			{
				slow->_right = fast->_left;
			}
			else				
			{ 
				slow->_left = fast->_left;
			}
			delete fast;
			fast = nullptr;
		}
		return true;
	}

private:
	Node* _root = nullptr;
};
